package com.hanxiaozhang.no10leetcode.string;

import java.util.Stack;

/**
 * 〈一句话功能简述〉<br>
 * 〈在给定的字符串中找到最长的回文子字符串，假定字符串最大长度为1000〉
 * 实例1:
 * 输入: "babad"
 * 输出: "bab"
 * Tips: "aba" 也是一个有效的答案.
 * 实例2:
 * 输入: "cbbd"
 * 输出: "bb"
 * <p>
 * 提示：
 * 回文字符串，分为：奇数回文（abcba）和偶数回文（abba）
 * <p>
 * 思路：
 * 1.回文字找出中心位置，判断左右两侧对称位置元素的相等个数
 * 2.回文字符串，分为：奇数回文（abcba）和偶数回文（abba），需要处理两次
 * 3. 中心位置，处理左右边界：
 *  - 中心位加减maxlength/2正好得到左右边界，如果是偶数个字符的话，那么maxlength/2将会导致左边界多减了1。
 *  - 计算左边界时，要用（maxlength - 1）/2，因为在java的除运算中，奇数 与 (奇数 -1) /2的结果相同，
 *  - 但是偶数减一后结果值小1，符号左边界值。
 *
 *
 * @author hanxinghua
 * @create 2024/1/8
 * @since 1.0.0
 */
public class No5LongestPalindromicSubstring {


    public static void main(String[] args) {

        String s1 = "babad";
        String s2 = "cbbd";
        String s3 = "12345a54321abc";
        String s4 = "a";

        System.out.println(longestPalindrome(s4));
    }

    /**
     * 方法1：
     * <p>
     * 思路：
     * 回文字找出中心位置，判断左右两侧对称位置元素的相等个数
     *
     * @param s
     * @return
     */
    public static String longestPalindrome(String s) {
        // 极值判断
        if (s == null || s.length() < 1) {
            return "";
        }
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            // 模拟奇数回文  ->  abcba
            int len1 = expandAroundCenter(s, i, i);
            // 模拟偶数回文 ->  abba
            int len2 = expandAroundCenter(s, i, i + 1);
            int len = Math.max(len1, len2);

            // 本次长度，与历史长度比较
            if (len > end - start) {

                // 中心位加减maxlength/2正好得到左右边界，如果是偶数个字符的话，那么maxlength/2将会导致左边界多减了1。
                // 计算左边界时，要用（maxlength - 1）/2，因为在java的除运算中，奇数 与 (奇数 -1) /2的结果相同，
                // 但是偶数减一后结果值小1，符号左边界值。

                // 计算左边界（重要）：
                start = i - (len - 1) / 2;
                // 计算右边界：
                end = i + len / 2;
            }
        }
        return s.substring(start, end + 1);
    }


    /**
     * 回文长度
     *
     * @param s     字符串
     * @param left  左边界
     * @param right 右边界
     * @return 长度
     */
    private static int expandAroundCenter(String s, int left, int right) {
        int L = left, R = right;
        while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
            L--;
            R++;
        }
        return R - L - 1;
    }

}
